package a08_回溯算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * <p>
 * a05_电话号码的字母组合复习3
 * </p>
 *
 * @author flyduck
 * @since 2025/4/8
 */
public class a05_电话号码的字母组合复习3 {
    public static void main(String[] args) {
        a05_电话号码的字母组合复习3 test = new a05_电话号码的字母组合复习3();
        System.out.println(test.letterCombinations(""));
    }
    public List<String> letterCombinations(String digits) {
        char[][] grid = new char[][]{
            {' ',' ',' ',' '},
            {' ',' ',' ',' '},
            {'a','b','c',' '},
            {'d','e','f',' '},
            {'g','h','i',' '},
            {'j','k','l',' '},
            {'m','n','o',' '},
            {'p','q','r','s'},
            {'t','u','v',' '},
            {'w','x','y','z'}
        };
        char[] chars = digits.toCharArray();
        int[] nums = new int[chars.length];
        for (int i = 0; i < chars.length; i++) {
            nums[i] = Integer.valueOf(chars[i] + "");
        }

        List<String> result = new ArrayList<>();
        if (digits.equals("")) {
            return result;
        }
        LinkedList<Character> path = new LinkedList<>();
        traversal(result, path, grid, nums, 0);
        return result;
    }

    private void traversal(List<String> result,
                           LinkedList<Character> path,
                           char[][] grid,
                           int[] nums,
                           int startIdx){
        if (startIdx == nums.length) {
            String collect = path.stream()
                    .map(item -> item + "")
                    .collect(Collectors.joining(""));
            result.add(collect);
            return;
        }
        for (int i = 0; i < grid[nums[startIdx]].length; i++) {
            if(grid[nums[startIdx]][i] == ' '){
                continue;
            }
            path.add(grid[nums[startIdx]][i]);
            traversal(result, path, grid, nums, startIdx + 1);
            path.removeLast();
        }
    }
}
